/*
 * @lc app=leetcode.cn id=230 lang=typescript
 *
 * [230] 二叉搜索树中第K小的元素
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

//  思路：BST树的中序遍历就是升序的
//  通过rank代表index作为当前的排序，如果与k一直则得到解

//  复杂度：O(n) O(1)

function kthSmallest(root: TreeNode | null, k: number): number {
    let res = 0, rank = 0
    const traverse = (root: TreeNode | null, k: number): void => {
        if (!root) return
        traverse(root.left, k)
        //  中序遍历
        rank++
        if (rank === k) {
            res = root.val
            return
        }
        traverse(root.right, k)
    }
    traverse(root, k)
    return res
};
// @lc code=end

import { TreeNode } from "./type"

const root = TreeNode.buildTree([3, 1, 4, null, 2])
const root2 = TreeNode.buildTree([5, 3, 6, 2, 4, null, null, 1])
// console.log(TreeNode.printTree(root))
console.log(kthSmallest(root, 1))
console.log(kthSmallest(root2, 3))
